/**
 * 15. 三数之和
 * https://leetcode-cn.com/problems/3sum/
 */
const { displayNestedArray } = require('../../libs/public');

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function threeSum(nums) {
  if (nums.length < 3) return [];
  nums.sort((a, b) => a - b);
  const result = [];
  const last = nums.length - 2;
  let i = 0;
  while (i < last) {
    const curVal = nums[i];
    const target = -curVal;
    let left = i + 1;
    let leftVal = 0;
    let right = nums.length - 1;
    let rightVal = 0;
    while (left < right) {
      leftVal = nums[left];
      rightVal = nums[right];
      const sum = leftVal + rightVal;
      if (sum === target) {
        result.push([curVal, leftVal, rightVal]);
        left += 1;
        while (left < nums.length && nums[left] === leftVal) {
          left += 1;
        }
        while (nums[right - 1] === rightVal) {
          right -= 1;
        }
      } else if (sum < target) {
        left += 1;
      } else {
        right -= 1;
      }
    }
    i += 1;
    while (nums[i] === curVal) {
      i += 1;
    }
  }
  return result;
}

console.log(displayNestedArray(threeSum([-1, 0, 1, 2, -1, -4])) === '[[-1,-1,2],[-1,0,1]]');
console.log(displayNestedArray(threeSum([])) === '[]');
console.log(displayNestedArray(threeSum([0])) === '[]');
